package leetcode.pre100;

import utils.ListNode;

/**
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 * <p>
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 * <p>
 * 示例:
 * <p>
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 * <p>
 *
 * @since 2020/6/10 0010 下午 8:59
 */
public class Code92_ReverseListBetween {
    /**
     * 找到第m-1个节点，第m个节点，以及第n个节点，第n+1个节点
     */
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null) return head;
        ListNode newHead = new ListNode(-1);
        ListNode pre = newHead;
        pre.next = head;
        ListNode start = pre;
        ListNode end = pre;
        //找到第m-1个点,如m=1，要先找到pre，然后在再找到head
        while (--m != 0) {
            start = start.next;
            end = end.next;
            n--;
        }
        pre = start;
        start = start.next;
        while (n-- != 0) {
            end = end.next;
        }
        //找到第n个节点和第n+1个节点
        ListNode next = end.next;
        doReverse(start, end);
        pre.next = end;
        start.next = next;
        return newHead.next;
    }

    private void doReverse(ListNode start, ListNode end) {
        ListNode pre = null;
        while (true) {
            ListNode next = start.next;
            //把start和pre连接起来
            start.next = pre;
            pre = start;
            if (start == end) return;
            start = next;
        }
    }
}
